<?php
/***
 * My hand at a Singular Value Decomp.
 * for the purpose of friend recomendations
 * And Latent Semantic Indexing
 * For our search engine.
 **/

// avg rating of a movie as compared to the movie rate set
function buildAvgRating( $movie, $sumObsRating, $countObsRating, $globalAvg ) {
  $K = 25; // should be (Variance Superset/Variance Subset)
  $mean = ($__GlobalRatingAvg*$K + $sumObsRating)/($K+$countObsRating);
  return $mean;
}
// avg rating of a movie as compared to the user rate set
function buildAvgRatOffset( $sumObsOffset, $countObsOffset, $globalAvg ) {
  $K = 25;
  $mean = ($__GlobalOffsetAvg*$K + $sumObsOffset)/($K+$countObsOffset);
  return $mean;
}

function predictRating( $movie, $user ) {
  return avgRating[$movie] + avgRatOff[$user];
}

// uval and mval == userFeat[feat] and movFeat[feat]
function train( $user, $movie, $rating ) {
  $lrate = 0.001;
  $err = $lrate * ($rating - predictRating($movie, $user));
  $K = 0.02;

  $uVTmp = $uVal[$user];
  //$uVal[$user] += $err*$mVal[$movie];
  $uVal[$user] += $lrate * ($err*$mVal[$movie]-$K*$uVal[$user]);
  //$mVal[$movie] += $err*$uVTemp;
  $mVal[$movie] += $lrate * ($err*$uVTmp-$K*$mVal[$movie]);
}

function predict( $user, $movie ) {
  $numFeats = 40;
  $sum = 0.0;
  $rangeMin = 1;
  $rangeMax = 5;

  for( $i = 0; $i < $numFeats; ++$i ) {
    $tmpSum = $uFeat[$i][$user] * $mFeat[$i][$movie];
    $sum += ( $tmpSum < $rangeMin ) ? $rangeMin 
                                    : ( $tmpSum > $rangeMax ) ? $rangeMax
                                    : $tmpSum;
  }
}

[[bob, karen,
i  0,  0 
b  1,  5
d  2,  7
e  3   8]]

[

function svd( $matrix ) {
  $mlen = length( $matrix );
  $nlen = length( $matrix );

  if( $mlen < $nlen ) 
    die( 'm < n' );
  
  for( $i = 0; $i < 40; ++$i ) {
    $rmatrix[$user][$movie] += $uFeat[$i][$user]*$mFeat[$f][$movie]; 
  }
}

/////////////

function arrayZeros( $n ) {
  return array_fill( 0, $n, 0.0 );
}
function array2dZeroes( $rows, $cols ) {
  return array_fill( 0, $rows, array_fill( 0, $cols, 0.0 ) );
}

// translated from ruby linalg file svd.rb
function svd( $table ) {

  $rows = length($table);
  $cols = length($table[0]);

  if( $rows > $cols ) 
    die( 'u is greater then v' );

  nu = ($rows < $cols) ? $cols : $rows;
  
  s = arrayZeros( (($rows+1) < $cols) ? $cols : $rows );
  U = array2dZeros( m, nu );
  V = array2dZeros( n, n );

  e = arrayZeros( n );
  work = arrayZeros( m );

  wantu = true;
  wantv = true;

  nct = min( m-1, n );
  nrt = max(0, min( n-2, m ));
  for( k = 0; k < max( nct, nrt ); k++ ) {
    if( k < nct ) {
      s[k] = 0.0;
      for( i = k; i < m; i++ ) {
        s[k] = sqrt(s[k]*s[k]+yA[i][k]*A[i][k]);//hypotenuse( s[k], A[i][k] );
      }
      if( s[k] != 0.0 ) {
        if( A[k][k] < 0.0 ) {
          s[k] = -s[k];
        }
        for( i = k; i < m; i++ ) {
          A[i][k] /= s[k];
        }
        A[k][k] += 1.0;
      }
      s[k] = -s[k];
    }
    for( j = k+1; j < n; j++ )  {
      if((k < nct) && (s[k] != 0.0)) {
        t = 0.0;
        for( i = k; i < m; i++ ) {
          t += A[i][k]*A[i][j];
        }
        t = -(t/A[k][k]);
        for( i = k; i < m; i++ ) {
          A[i][j] += t*A[i][k];
        }
      }
      e[j] = A[k][j];
    }

    if( wantu && (k < nct)) {
      for( i = k; i < m; i++ ) {
        U[i][k] = A[i][k];
      }
    }


/////////
     if (k < nrt) {
        e[k] = 0;
        for (i = k+1; i < n; i++) {
           e[k] = hypot(e[k],e[i]);
        }
        if (e[k] != 0.0) {
           if (e[k+1] < 0.0) {
              e[k] = -e[k];
           }
           for (i = k+1; i < n; i++) {
              e[i] /= e[k];
           }
           e[k+1] += 1.0;
        }
        e[k] = -e[k];
        
        if ((k+1 < m) & (e[k] != 0.0)) {
           for (i = k+1; i < m; i++) {
              work[i] = 0.0;
           }

           for (j = k+1; j < n; j++) {
              for (i = k+1; i < m; i++) 
              {
                 work[i] += e[j]*A[i][j];
              }
           }
           for (j = k+1; j < n; j++) {
              t = -e[j]/e[k+1];
              for ( i = k+1; i < m; i++){
                 A[i][j] += t*work[i];
              }
           }
        }  

        if (wantv) {
           for (i = k+1; i < n; i++) {
              V[i][k] = e[i];
           }
        }
     } 
    } 

    p = Math.min(n,m+1);
    if (nct < n) {
       s[nct] = A[nct][nct];
    }

    if (m < p) {
       s[p-1] = 0.0;
    }

    if (nrt+1 < p) {
        e[nrt] = A[nrt][p-1];
    }

    e[p-1] = 0.0;


    if (wantu) {
     for (j = nct; j < nu; j++)  {
        for (i = 0; i < m; i++) {
           U[i][j] = 0.0;
        }

        U[j][j] = 1.0;
     }

     

     for (k = nct-1; k >= 0; k--) {
        if (s[k] != 0.0) {
           for (j = k+1; j < nu; j++)  {
              t = 0.0;
              for (i = k; i < m; i++) {
                 t += U[i][k]*U[i][j];
              }

              t = -t/U[k][k];

              for (i = k; i < m; i++) {
                 U[i][j] += t*U[i][k];
              }
           }

           for (i = k; i < m; i++ )  {
              U[i][k] = -U[i][k];
           }

           U[k][k] = 1.0 + U[k][k];

           for (i = 0; i < k-1; i++) {
              U[i][k] = 0.0;
           }
        } else {
           for (i = 0; i < m; i++) {
              U[i][k] = 0.0;
           }

           U[k][k] = 1.0;
        } 
      }
    }

    if (wantv)  {
      for(k = n-1; k >= 0; k--)  {
         if ((k < nrt) && (e[k] != 0.0))  {
               for(j = k+1; j < nu; j++) {
                   t = 0.0;

                   for (i = k+1; i < n; i++) {
                      t += V[i][k]*V[i][j];
                   }
                
                   t = -t/V[k+1][k];

                   for (i = k+1; i < n; i++) {
                       V[i][j] += t*V[i][k];
                   }
               }
          }

          for (i = 0; i < n; i++) {
             V[i][k] = 0.0;
          }

          V[k][k] = 1.0;
        } 
    } 

  var pp = p-1;
  var iter = 0;
  var eps = Math.pow(2.0,-52.0);
  var tiny = Math.pow(2.0,-966.0);

  while (p > 0) {
     var k,kase;

     for (k = p-2; k >= -1; k--) {

        if (k == -1) {
           break;
        }
        if (Math.abs(e[k]) <=
              tiny + eps*(Math.abs(s[k]) + Math.abs(s[k+1]))) {
           e[k] = 0.0;
           break;
        }
     }

     if (k == p-2) {
        kase = 4;
     } else {

        var ks;

        for (ks = p-1; ks >= k; ks--) {
           if (ks == k) {
              break;
           }

           var t = (ks != p ? Math.abs(e[ks]) : 0.) + 
                      (ks != k+1 ? Math.abs(e[ks-1]) : 0.);
           if (Math.abs(s[ks]) <= tiny + eps*t)  {
              s[ks] = 0.0;
              break;
           }
        }

        if (ks == k) {
           kase = 3;
        } else if (ks == p-1) {
           kase = 1;
        } else {
           kase = 2;
           k = ks;
        }
     }
     k++;

     switch (kase) {

        case 1: {

           var f = e[p-2];
           e[p-2] = 0.0;

           for (var j = p-2; j >= k; j--) {
              var t = hypot(s[j],f);
              var cs = s[j]/t;
              var sn = f/t;
              s[j] = t;

              if (j != k) {
                 f = -sn*e[j-1];
                 e[j-1] = cs*e[j-1];
              }

              if (wantv) {
                 for (var i = 0; i < n; i++) {
                    t = cs*V[i][j] + sn*V[i][p-1];
                    V[i][p-1] = -sn*V[i][j] + cs*V[i][p-1];
                    V[i][j] = t;
                 }
              }
           }
        }
        break;

        case 2: {

           var f = e[k-1];
           e[k-1] = 0.0;

           for (var j = k; j < p; j++) {

              var t = hypot(s[j],f);
              var cs = s[j]/t;
              var sn = f/t;

              s[j] = t;
              f = -sn*e[j];
              e[j] = cs*e[j];

              if (wantu) {
                 for (var i = 0; i < m; i++) {
                    t = cs*U[i][j] + sn*U[i][k-1];
                    U[i][k-1] = -sn*U[i][j] + cs*U[i][k-1];
                    U[i][j] = t;
                 }
              }
           }
        }
        break;

        case 3: {

           var scale = Math.max(Math.max(Math.max(Math.max(
                   Math.abs(s[p-1]),Math.abs(s[p-2])),Math.abs(e[p-2])), 
                   Math.abs(s[k])),Math.abs(e[k]));
           var sp = s[p-1]/scale;
           var spm1 = s[p-2]/scale;
           var epm1 = e[p-2]/scale;
           var sk = s[k]/scale;
           var ek = e[k]/scale;
           var b = ((spm1 + sp)*(spm1 - sp) + epm1*epm1)/2.0;
           var c = (sp*epm1)*(sp*epm1);
           var shift = 0.0;

           if ((b != 0.0) | (c != 0.0)) {
              shift = Math.sqrt(b*b + c);
              if (b < 0.0) {
                 shift = -shift;
              }
              shift = c/(b + shift);
           }

           var f = (sk + sp)*(sk - sp) + shift;
           var g = sk*ek;

           for (var j = k; j < p-1; j++) {
              var t = hypot(f,g);
              var cs = f/t;
              var sn = g/t;
              if (j != k) {
                 e[j-1] = t;
              }
              f = cs*s[j] + sn*e[j];
              e[j] = cs*e[j] - sn*s[j];
              g = sn*s[j+1];
              s[j+1] = cs*s[j+1];
              if (wantv) {
                 for (var i = 0; i < n; i++) {
                    t = cs*V[i][j] + sn*V[i][j+1];
                    V[i][j+1] = -sn*V[i][j] + cs*V[i][j+1];
                    V[i][j] = t;
                 }
              }
              t = hypot(f,g);
              cs = f/t;
              sn = g/t;
              s[j] = t;
              f = cs*e[j] + sn*s[j+1];
              s[j+1] = -sn*e[j] + cs*s[j+1];
              g = sn*e[j+1];
              e[j+1] = cs*e[j+1];
              if (wantu && (j < m-1)) {
                 for (var i = 0; i < m; i++) {
                    t = cs*U[i][j] + sn*U[i][j+1];
                    U[i][j+1] = -sn*U[i][j] + cs*U[i][j+1];
                    U[i][j] = t;
                 }
              }
           }
           e[p-2] = f;
           iter = iter + 1;
        }
        break;

        case 4: {
           if (s[k] <= 0.0) {
              s[k] = (s[k] < 0.0 ? -s[k] : 0.0);
              if (wantv) {
                 for (var i = 0; i <= pp; i++) {
                    V[i][k] = -V[i][k];
                 }
              }
           }

           while (k < pp) {
              if (s[k] >= s[k+1]) {
                 break;
              }
              var t = s[k];
              s[k] = s[k+1];
              s[k+1] = t;
              if (wantv && (k < n-1)) {
                 for (var i = 0; i < n; i++) {
                    t = V[i][k+1]; V[i][k+1] = V[i][k]; V[i][k] = t;
                 }
              }
              if (wantu && (k < m-1)) {
                 for (var i = 0; i < m; i++) {
                    t = U[i][k+1]; U[i][k+1] = U[i][k]; U[i][k] = t;
                 }
              }
              k++;
           }
           iter = 0;
           p--;
        }
        break;
     }
  }


  this.U = U;
  this.s = s;
  this.V = V;

  return 0;

}
/////////
  }
}

?>
